package leetcode.code0698;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution3 implements IDebug {

	int[] nums;
	int len;
	int avg;

	public boolean canPartitionKSubsets(int[] nums, int k) {
		int sum = 0;
		for (int num : nums) {
			sum += num;
		}
		if (sum % k != 0) {
			return false;
		}
		this.nums = nums;
		this.len = nums.length;
		this.avg = sum / k;
		Boolean[][] dp = new Boolean[len][1 << len];
		return this.find(avg, 0, k - 1, 0, dp);
	}

	private boolean find(int avg, int index, int k, int used, Boolean[][] dp) {
		if (index == len) {
			return k == -1;
		}
		if (dp[index][used] != null) {
			return dp[index][used];
		}
		for (int i = 0; i < this.len; i++) {
			if (((1 << i) & used) == 0) {
				if (avg > this.nums[i]) {
					if (this.find(avg - nums[i], index + 1, k, used | (1 << i), dp)) {
						return true;
					}
				} else if (avg == this.nums[i]) {
					if (this.find(this.avg, index + 1, k - 1, used | (1 << i), dp)) {
						return true;
					}
				}
			}
		}
		dp[index][used] = false;
		return false;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(true, this.canPartitionKSubsets(HelpDebug.str2array3("[4,3,2,3,5,2,1]"), 4));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
//		[10,1,10,9,6,1,9,5,9,10,7,8,5,2,10,8]
//				11
		HelpDebug.compare(false, this.canPartitionKSubsets(HelpDebug.str2array3("[10,1,10,9,6,1,9,5,9,10,7,8,5,2,10,8]"), 11));
	}

	@Override
	public void debug3() {
		HelpDebug.compare(true, this.canPartitionKSubsets(HelpDebug.str2array3("[4,4,6,2,3,8,10,2,10,7]"), 4));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		HelpDebug.compare(true, this.canPartitionKSubsets(
				HelpDebug.str2array3("[3522,181,521,515,304,123,2512,312,922,407,146,1932,4037,2646,3871,269]"), 5));

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug4();
		so.debug2();
		so.debug3();
		so.debug1();

	}

}
